package com.dy.分类.哈希表和字符串._187_重复的DNA序列;

import java.util.*;

/*
所有 DNA 由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。

编写一个函数来查找 DNA 分子中所有出现超多一次的10个字母长的序列（子串）。

示例:

输入: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

输出: ["AAAAACCCCC", "CCCCCAAAAA"]
 */
public class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        List<String > res = new ArrayList<>();
        if(s.length()<10) return res;
        HashMap<String,Integer> map = new HashMap<>();
        for(int i=0;i<=s.length()-10;i++){
            String sub = s.substring(i,i+10);
            if(map.containsKey(sub)){
                map.put(sub,map.get(sub)+1);
            }
            else{
                map.put(sub,1);
            }
        }
        for(String k:map.keySet()){
            if(map.get(k)>1){
                res.add(k);
            }
        }
        return res;
    }

    public List<String> findRepeatedDnaSequences2(String s) {
        Set<String> set = new HashSet<>();
        Set<String> help = new HashSet<>();
        for(int i=0;i<=s.length()-10;i++){
            String cur = s.substring(i,i+10);
            if(!set.add(cur)) help.add(cur);
        }
        return new ArrayList<>(help);
    }
}
